#include "Search.h"
#include "Mouse.h"
#include<ctime>
#include<cstdlib>
#include<iostream>
using namespace std;
Search::Search()
{
}

void Search::initblock(int mode)//Initialize the obstacle
{
	int cnt;
	memset(mapp, 0, sizeof(mapp));
	memset(vis, 0, sizeof(vis));
	if (mode == map_mode_low)//Randomly generate the coordinates of 100 obstacles
	{
		cnt = 100;
		num = cnt;
		srand(time(0));
		for (int i = 0; i < cnt; i++)
		{
			mapp[rand() % 20][rand() % 20] = 1;
		}
		mapp[0][0] = 0;
		mapp[19][19] = 0;
	}
	if(mode==map_mode_high)//Randomly generate the coordinates of 150 obstacles
	{
		cnt = 150;
		num = cnt;
		srand(time(0));
		for (int i = 0; i < cnt; i++)
		{
			mapp[rand() % 20][rand() % 20] = 1;
		}
		mapp[0][0] = 0;

		mapp[19][19] = 0;
	}
	return;
}

bool Search::solve(int mode)//Use BFS algorithm  to find the shortest path
{
	int sx, sy, ex, ey;
	cout << "S" << S << endl;
	if (mode == point_users)//The starting and final points setted by yourself
	{
		sy = S / 100 ; sx = S % 100 ;//Get the real x and y
		ey = E / 100 ; ex = E % 100 ;
	}
	else//The starting and final points setted automatically
	{
		sx = 0;  sy = 0;
		ex = 19; ey = 19;
	}

	cout<<"sx " << sx << " "<<sy<<endl;
	head = 0;//The head of the queue
	tail = 0; //The tail of the queue
	q[head].x = sx; q[head].y = sy;//The coordinates of the start point
	q[head].pre = -1;//Record the leading node of the node
	vis[sx][sy] = 1;//Marks the point which has been searched
	tail++;

	while (head < tail)
	{
		for (int i = 0; i < 8; i++)// Searching points in eight directions
		{
			int x = q[head].x + d[i][0];//the coordinates of the next searching point
			int y = q[head].y + d[i][1];//the coordinates of the next searching point
			if (x < 0 || x>19 || y < 0 || y>19 || vis[x][y] || mapp[x][y] == 1)//Determine if the next search point is out of range, has been searched, or is a barrier
				continue;
			q[tail].x = x;//Record the coordinates of the next searching point
			q[tail].y = y;//Record the coordinates of the next searching point
			q[tail].pre = head;
			tail++;
			vis[x][y] = 1;//Marks the point that has been searched
			if (x == ex && y == ey) //Determine if the search ends
			{
				//for (int i = 0; i < tail; i++)
					//cout << i << " " << q[i].x << " " << q[i].y << " " << q[i].pre << endl;
				ans.clear();
				getroad(q[tail-1]);
				return true;
			}
		}
		head++;
	}
	return false;
}

void Search::getroad(Points t)//Find the shortest path with recursive algorithm
{
	if (t.pre == -1)//Recursive export
	{
		ans.push_back(t);
		return;
	}
	else 
	{
		getroad(q[t.pre]);//Find the leading node of this point
		ans.push_back(t);
		return;
	}
}


Search::~Search()
{
}
